
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def invertTree(self, root: TreeNode):
        if not isinstance(root, TreeNode):
            return root
        left = self.invertTree(root.left)  # 递归遍历二叉树的左子树
        right = self.invertTree(root.right)  # 递归遍历二叉树的右子树
        root.left, root.right = right, left  # 对应交换根节点的左右节点
        return root


def showtree(root):  # 从上往下打印二叉树
    A = []
    result = []
    if not isinstance(root, TreeNode):
        return root
    A.append(root)
    while A:
        print(len(A))
        current_root = A.pop(0)
        if not isinstance(current_root, TreeNode):
            result.append(current_root)
            continue
        result.append([current_root.val])
        if current_root.left:
            A.append(current_root.left)
        if current_root.right:
            A.append(current_root.right)
    print(result)

t1 = TreeNode(2)
t1.left = 1
t1.right = 3
t2 = TreeNode(7)
t2.left = 6
t2.right = 9
tree = TreeNode(4)
tree.left = t1
tree.right = t2

s = Solution()
out = s.invertTree(tree)
showtree(out)
